package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *BusRoutes_815 给定几趟巴士路线 问给定出发点和终点  最小换乘站
 *describe:用hashmap和BFS AC 60%
 *2018年10月27日 下午4:06:42
 */
public class BusRoutes_815 {
	public int numBusesToDestination(int[][] routes, int S, int T) {
        Map<Integer, Set<Integer>> bus_stops = new HashMap<>();
        Map<Integer, List<Integer>> stop_bus = new HashMap<>();
        for(int i = 0; i < routes.length; i++) {
            bus_stops.put(i, new HashSet<>());
            for(int s: routes[i]) {
                bus_stops.get(i).add(s);
            }
        }
        for(int i = 0; i < routes.length; i++) {
            int[] stops = routes[i];
            for(int stop: stops) {
                List<Integer> buses = stop_bus.getOrDefault(stop, new ArrayList<>());
                buses.add(i);
                stop_bus.put(stop, buses);
            }
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> que = new LinkedList<>();
        que.offer(S);
        int res = 0;
        while(!que.isEmpty()) {
            int sz = que.size();
            for(int i = 0; i < sz; i++) {
                int curStop = que.poll();
                if (curStop == T) return res;
                List<Integer> buses = stop_bus.get(curStop);
                for(int bus: buses) {
                    if (visited.contains(bus)) continue;
                    if (bus_stops.get(bus).contains(T)) return res + 1;
                    visited.add(bus);
                    que.addAll(bus_stops.get(bus));
                }
            }    
            res++;
        }
        return -1;
    }
}
